﻿int[] list = [1, 2, 4, 3, 5, 8, 9, 10, 11, 2, 3];
QuickSort(list, 0, list.Length - 1); // 调用快速排序
foreach (int i in list)
{
	Console.Write(i + " ");
}

/* 元素交换 */
void Swap(int[] nums, int i, int j) {
	(nums[j], nums[i]) = (nums[i], nums[j]);
}

/* 哨兵划分 */
int Partition(int[] nums, int left, int right) {
	int i = left, j = right;
	while (i < j) {
		while (i < j && nums[j] >= nums[left])
			j--;          // 从右向左找首个小于基准数的元素
		while (i < j && nums[i] <= nums[left])
			i++;          // 从左向右找首个大于基准数的元素
		Swap(nums, i, j); // 交换这两个元素
	}
	Swap(nums, i, left);  // 将基准数交换至分界线
	return i;             // 返回基准数的索引
}

/* 快速排序 */
void QuickSort(int[] nums, int left, int right) {
	if (left >= right) return;     // 子数组长度为1时终止
	int pivot = Partition(nums, left, right); // 划分操作
	QuickSort(nums, left, pivot - 1); // 递归左子数组
	QuickSort(nums, pivot + 1, right); // 递归右子数组
}
